Section: New Results

Neutrality in the Graph Coloring Problem

Participants: Marie-Eléonore Marmion, Aymeric Blot, Laetitia Jourdan, and Clarisse Dhaenens

The graph coloring problem is often investigated in the literature. Many insights about the existence of many neighboring solutions with the same fitness value are raised but as far as we know, no deep analysis of this neutrality has ever been conducted in the literature. We have quantified the neutrality of some hard instances of the graph coloring problem. This neutrality property has to be detected as it impacts the search process. Indeed, local optima may belong to plateaus that represents a barrier for local search methods. We also aim at pointing out the interest of exploiting neutrality during the search. Therefore, a generic local search dedicated to neutral problems (NILS) and previously tested on flowshop problems, is performed and tested on several hard instances. Results show that taking into account neutrality allows to obtain better results than when not considering it.